package com.review.backpack_01;

public class BP06 {
    //6. 分组背包问题
    //若干组物品，每一组只能选一个
    public int knapsackProblem(int[][] c, int[][] v, int cap) {
        int[] dp = new int[cap + 1];

        for (int i = 0; i < c.length; i++) {
            for (int j = cap; j >= 0; j--) {// 确保每个组中至多只有一个物品被选择
                for (int k = 0; k < c[i].length; k++) {
                    if (j >= c[i][k]) {
                        dp[j] = Math.max(dp[j], dp[j - c[i][k]] + v[i][k]);
                    }
                }
            }
        }
        return dp[cap];
    }

    public static void main(String[] args) {
        System.out.println(
                new BP06().knapsackProblem(
                        new int[][]{{1, 2, 3}, {2, 3, 4}, {5, 6, 7, 8}, {7, 9}},
                        new int[][]{{2, 3, 4}, {1, 2, 3}, {4, 5, 6, 7}, {8, 9}},
                        11
                )
        );
    }
}
